// https://leetcode.cn/problems/find-median-from-data-stream/description/

// 算法思路总结：
// 1. 使用最大堆存较小一半，最小堆存较大一半
// 2. 添加时先插入合适堆，再平衡两个堆的大小
// 3. 保持最大堆大小 >= 最小堆大小，且差值不超过1
// 4. 中位数：相等取平均，不等取最大堆顶
// 5. 时间复杂度：添加O(logn)，查找O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <queue>
#include <algorithm>

class MedianFinder 
{
public: 
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    MedianFinder()  
    {}
    
    // void addNum(int num) 
    // {
    //     maxHeap.push(num);
    //     minHeap.push(maxHeap.top());
    //     maxHeap.pop();

    //     if (minHeap.size() > maxHeap.size())
    //     {
    //         maxHeap.push(minHeap.top());
    //         minHeap.pop();
    //     }
    // }

    void addNum(int num) 
    {
        int m = maxHeap.size(), n = minHeap.size();

        if (m == n)
        {
            if (m == 0 || num <= minHeap.top())
                maxHeap.push(num);
            else
            {
                minHeap.push(num);
                int top = minHeap.top();
                minHeap.pop();
                maxHeap.push(top);
            }
        }
        else
        {
            if (num >= maxHeap.top())
                minHeap.push(num);
            else
            {
                maxHeap.push(num);
                int top = maxHeap.top();
                maxHeap.pop();
                minHeap.push(top);
            }
        }
    }
    
    double findMedian() 
    {
        int m = maxHeap.size(), n = minHeap.size();

        if (m == n) return (maxHeap.top() + minHeap.top()) / 2.0;
        else return (double)maxHeap.top();
    }
};

int main()
{

    MedianFinder* obj = new MedianFinder();

    obj->addNum(1);
    obj->addNum(2);

    double obj1 = obj->findMedian();

    obj->addNum(3);

    double obj2 = obj->findMedian();

    cout << obj1 << " " << obj2 << endl;

    return 0;
}